239. Sliding Window Maximum
Hard

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

 

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

Input: nums = [1], k = 1
Output: [1]

Example 3:

Input: nums = [1,-1], k = 1
Output: [1,-1]

Example 4:

Input: nums = [9,11], k = 2
Output: [11]

Example 5:

Input: nums = [4,-2], k = 2
Output: [4]

 

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length
Accepted
407,770
Submissions
905,588
Seen this question in a real interview before?
Show Hint 1
How about using a data structure such as deque (double-ended queue)?
Show Hint 2
The queue size need not be the same as the window’s size.
Show Hint 3
Remove redundant elements and the queue should store only elements that need to be considered.

Average Rating: 4.05 (166 votes)

Premium

Solution


Approach 1: Use a Hammer (Bruteforce)

Intuition

The straightforward solution is to iterate over all sliding windows and find a maximum for each window. There are N - k + 1 sliding windows and there are k elements in each window, that results in a quite bad time complexity O(Nk)\mathcal{O}(N k).

As you can imagine, this straightforward solution would result in TLE (Time Limit Exceed) exception.

It is correct though, one could start with this solution during the interview and improve it later on.

Implementation

Complexity Analysis

  • Time complexity : O(Nk)\mathcal{O}(N k), where N is number of elements in the array.

  • Space complexity : O(Nk+1)\mathcal{O}(N - k + 1) for an output array.


Approach 2: Deque

Intuition

How one could improve the time complexity? The first idea is to use a heap, since in a maximum heap heap[0] is always the largest element. Though to add an element in a heap of size k costs log(k)\log(k), that means O(Nlog(k))\mathcal{O}(N \log(k)) time complexity for the solution.

Could we figure out O(N)\mathcal{O}(N) solution?

Let's use a deque (double-ended queue), the structure which pops from / pushes to either side with the same O(1)\mathcal{O}(1) performance.

It's more handy to store in the deque indexes instead of elements since both are used during an array parsing.

Algorithm

The algorithm is quite straigthforward :

  • Process the first k elements separately to initiate the deque.

  • Iterate over the array. At each step :

    • Clean the deque :

      • Keep only the indexes of elements from the current sliding window.

      • Remove indexes of all elements smaller than the current one, since they will not be the maximum ones.

    • Append the current element to the deque.

    • Append deque[0] to the output.

  • Return the output array.

Implementation

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N), since each element is processed exactly twice - it's index added and then removed from the deque.

  • Space complexity : O(N)\mathcal{O}(N), since O(Nk+1)\mathcal{O}(N - k + 1) is used for an output array and O(k)\mathcal{O}(k) for a deque.


Approach 3: Dynamic programming

Intuition

Here is another O(N)\mathcal{O}(N) solution. The good thing about this solution is that you don't need any data structures but array / list.

The idea is to split an input array into blocks of k elements. The last block could contain less elements if n % k != 0.

split

The current sliding window with the first element i and the last element j could be placed inside one block, or in two different blocks.

split

The situation 1 is simple. Let's use an array left, where left[j] is a maximum element from the beginning of the block to index j, direction left->right.

split

To work with more complex situation 2, let's introduce array right, where right[j] is a maximum element from the end of the block to index j, direction right->left. right is basically the same as left, but in the other direction.

split

These two arrays together give all the information about window elements in both blocks. Let's consider a sliding window from index i to index j. By definition, element right[i] is a maximum element for window elements in the leftside block, and element left[j] is a maximum element for window elements in the rightside block. Hence the maximum element in the sliding window is max(right[i], left[j]).

split

Algorithm

The algorithm is quite straightforward :

  • Iterate along the array in the direction left->right and build an array left.

  • Iterate along the array in the direction right->left and build an array right.

  • Build an output array as max(right[i], left[i + k - 1]) for i in range (0, n - k + 1).

Implementation

Current
1 / 6

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N), since all we do is 3 passes along the array of length N.

  • Space complexity : O(N)\mathcal{O}(N) to keep left and right arrays of length N, and output array of length N - k + 1.

Report Article Issue

Comments: 87
willye's avatar
Read More

Another way of explaining the deque method (approach 2): You want to ensure the deque window only has decreasing elements. That way, the leftmost element is always the largest.

205
Show 7 replies
Reply
Share
Report
eefiasfira's avatar
Read More

Great explanation. Please note that it is misleading to include the output array in the space complexity - this makes solution 2 and 3 seem identical when in fact solution 2 is superior.
Solution 1 takes O(nk) time and O(1) space
Solution 2 takes O(n) time and O(k) space
Solution 3 takes O(n) time and O(n) space.
The optimal solution is 2.

77
Show 8 replies
Reply
Share
Report
sankalp's avatar
Read More

Third solution is brilliant brother.

59
Reply
Share
Report
moonlight16's avatar
Read More

Wow, when I read this sentence it totally confusese me!!!
"
How one could improve the time complexity? The first idea is to use a heap, since in a maximum heap heap[0] is always the largest element. Though to add an element in a heap of size k costs \log(k)log(k), that means \mathcal{O}(N \log(k))O(Nlog(k)) time complexity for the solution."

Can someone explain this out some more? The first idea is to use a heap. How so?

77
Show 16 replies
Reply
Share
Report
ricace's avatar
Read More

I think the thought behind solution 2 is monotonous stack/queue, and here Deque is to poll from both head and tail

32
Show 1 reply
Reply
Share
Report
lenchen1112's avatar
Read More

I don't think the approach 3 meet the description of this question. We are told that You can only see the k numbers in the window which means we should treat it as a data stream instead of a static data list. Therefore we shouldn't do any preprocess on it.

69
Show 1 reply
Reply
Share
Report
genehacker's avatar
Read More

For solution 2, we don't have to explicitly have a different way to keep track of max element, from 1..k and k..n separately. We can combine into same logic.

    # init deque and output
    deq = deque()
    output = []   # initialize
    for i in range(k):
        clean_deque(i)
        deq.append(i)

    output.append(nums[deq[0]])  # just add max once after the loop
    
    # build output
    for i in range(k, n):
        clean_deque(i)          
        deq.append(i)
        output.append(nums[deq[0]])
    return output

23
Show 1 reply
Reply
Share
Report
winterchocolatte's avatar
Read More

Shouldn't the heap implementation be O(nk) not O(nlogk) because removing a non maximal element is an O(k) operation? Only the adding of an element is O(logk) in this implementation. Would appreciate it if someone could clarify this.

17
Show 5 replies
Reply
Share
Report
darxsys's avatar
Read More

The second solution is really poorly explained.

12
Reply
Share
Report
jianchao-li's avatar
Read More

The third solution is really elegant. Rewrote in C++.

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (nums.empty()) {
            return {};
        }
        int n = nums.size();
        vector<int> left(n, 0), right(n, 0), ans(n - k + 1);
        left[0] = nums[0];
        right[n - 1] = nums[n - 1];
        for (int l = 1; l < n; l++) {
            left[l] = l % k ? max(left[l - 1], nums[l]) : nums[l];
            int r = n - l - 1;
            right[r] = (r + 1) % k ? max(nums[r], right[r + 1]) : nums[r];
        }
        for (int i = 0; i < n - k + 1; i++) {
            ans[i] = max(right[i], left[i + k - 1]);
        }
        return ans;
    }
};

11
Show 2 replies
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
03/10/2021 13:11Accepted368 ms189.6 MBcpp
03/10/2021 13:08Wrong AnswerN/AN/Acpp
03/10/2021 12:52Wrong AnswerN/AN/Acpp
03/10/2021 12:51Wrong AnswerN/AN/Acpp
03/10/2021 12:35Wrong AnswerN/AN/Acpp
03/10/2021 12:34Time Limit ExceededN/AN/Acpp
03/10/2021 12:33Time Limit ExceededN/AN/Acpp
03/10/2021 12:32Wrong AnswerN/AN/Acpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.